/*
 * @lc app=leetcode.cn id=155 lang=cpp
 *
 * [155] 最小栈 用两个栈，一个栈存数据，一个栈存各阶段最小数
 */

// @lc code=start

#include <iostream>       // std::cout
#include <stack>          // std::stack

class MinStack {

private:
  // 存数据
  stack<int> s1;
  // 存各阶段最小数
  stack<int> s2;

public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
      s1.push(x);
      if(s2.empty() || x<=s2.top())
      {
        // 如果s2为空，或者存入数小于等于之前最小数，则传入s2
        s2.push(x);
      }
        
    }
    
    void pop() {
      // 如果pop的是当前极小值，则s2也跟着pop
      if(s1.top()==s2.top())
      {
        s2.pop();
      }
      s1.pop();
    }
    
    int top() {
      return s1.top();
    }
    
    int getMin() {
      // 栈顶元素为当前最小数
      return s2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
// @lc code=end

